#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn = 3e5 + 10;
const int inf=2e18;
int dist[maxn]; // 1 到 i 节点之间的距离
bool vis[maxn];

struct Node{
	// 存到优先级队列里面时表示 1到 x 最短距离为 w
	int x,w; // 存图时表示 到 x 有一条 权值为 w 的边
	// 小根堆, 此时存的是节点
	bool operator < (const Node & nd) const { // 注意这里面必须是两个 const  
		return w==nd.w?x<nd.x:w>nd.w;// 注意 pq 的小根堆 使用的是 >
	}
};

int n,m;
vector<Node> adj[maxn];

void dijkstra(int st){
	priority_queue<Node> pq;
	pq.push({st, dist[st]=0});
	while(pq.size()){
		auto [x, ds]=pq.top();pq.pop(); // 节点, 注意此处一定不能使用 & 因为 你已经把它从队列中弹出来了, &使用的还是之前的地址
		if(vis[x]){ // 之前是最小值, 已经确定过了
			continue;
		}
		vis[x]=true;
		for(const auto& [y, w]: adj[x]){
			if(ds+w<dist[y]){ // 找到更近的路了
				dist[y]=ds+w;
				pq.push({y, dist[y]});
			}
		}
	}
}

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){ // 到每个节点的距离初始化为最大值
		dist[i]=inf;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({v, w});
	}
	dijkstra(1);
	for(int i=1;i<=n;i++){
		cout<<(dist[i]>=inf?-1:dist[i])<<' ';
	}
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
